Search Results

Documents authored by Wootters, Mary

Document
DOI: 10.4230/LIPIcs.ITCS.2024.16
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications

Authors: Keller Blackwell and Mary Wootters

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
A Homomorphic Secret Sharing (HSS) scheme is a secret-sharing scheme that shares a secret x among s servers, and additionally allows an output client to reconstruct some function f(x), using information that can be locally computed by each server. A key parameter in HSS schemes is download rate, which quantifies how much information the output client needs to download from each server. Recent work (Fosli, Ishai, Kolobov, and Wootters, ITCS 2022) established a fundamental limitation on the download rate of linear HSS schemes for computing low-degree polynomials, and gave an example of HSS schemes that meet this limit. In this paper, we further explore optimal-rate linear HSS schemes for polynomials. Our main result is a complete characterization of such schemes, in terms of a coding-theoretic notion that we introduce, termed optimal labelweight codes. We use this characterization to answer open questions about the amortization required by HSS schemes that achieve optimal download rate. In more detail, the construction of Fosli et al. required amortization over 𝓁 instances of the problem, and only worked for particular values of 𝓁. We show that - perhaps surprisingly - the set of 𝓁’s for which their construction works is in fact nearly optimal, possibly leaving out only one additional value of 𝓁. We show this by using our coding-theoretic characterization to prove a necessary condition on the 𝓁’s admitting optimal-rate linear HSS schemes. We then provide a slightly improved construction of optimal-rate linear HSS schemes, where the set of allowable 𝓁’s is optimal in even more parameter settings. Moreover, based on a connection to the MDS conjecture, we conjecture that our construction is optimal for all parameter regimes.
Cite as

Keller Blackwell and Mary Wootters. A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blackwell_et_al:LIPIcs.ITCS.2024.16,
  author =	{Blackwell, Keller and Wootters, Mary},
  title =	{{A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.16},
  URN =		{urn:nbn:de:0030-drops-195447},
  doi =		{10.4230/LIPIcs.ITCS.2024.16},
  annote =	{Keywords: Error Correcting Codes, Homomorphic Secret Sharing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.55
High-Probability List-Recovery, and Applications to Heavy Hitters

Authors: Dean Doron and Mary Wootters

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
An error correcting code 𝒞 : Σ^k → Σⁿ is efficiently list-recoverable from input list size 𝓁 if for any sets ℒ₁, …, ℒ_n ⊆ Σ of size at most 𝓁, one can efficiently recover the list ℒ = {x ∈ Σ^k : ∀ j ∈ [n], 𝒞(x)_j ∈ ℒ_j}. While list-recovery has been well-studied in error correcting codes, all known constructions with "efficient" algorithms are not efficient in the parameter 𝓁. In this work, motivated by applications in algorithm design and pseudorandomness, we study list-recovery with the goal of obtaining a good dependence on 𝓁. We make a step towards this goal by obtaining it in the weaker case where we allow a randomized encoding map and a small failure probability, and where the input lists are derived from unions of codewords. As an application of our construction, we give a data structure for the heavy hitters problem in the strict turnstile model that, for some parameter regimes, obtains stronger guarantees than known constructions.
Cite as

Dean Doron and Mary Wootters. High-Probability List-Recovery, and Applications to Heavy Hitters. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.ICALP.2022.55,
  author =	{Doron, Dean and Wootters, Mary},
  title =	{{High-Probability List-Recovery, and Applications to Heavy Hitters}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.55},
  URN =		{urn:nbn:de:0030-drops-163961},
  doi =		{10.4230/LIPIcs.ICALP.2022.55},
  annote =	{Keywords: List recoverable codes, Heavy Hitters, high-dimensional expanders}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.71
On the Download Rate of Homomorphic Secret Sharing

Authors: Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, and Mary Wootters

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that supports evaluating functions on shared secrets by means of a local mapping from input shares to output shares. We initiate the study of the download rate of HSS, namely, the achievable ratio between the length of the output shares and the output length when amortized over 𝓁 function evaluations. We obtain the following results. - In the case of linear information-theoretic HSS schemes for degree-d multivariate polynomials, we characterize the optimal download rate in terms of the optimal minimal distance of a linear code with related parameters. We further show that for sufficiently large 𝓁 (polynomial in all problem parameters), the optimal rate can be realized using Shamir’s scheme, even with secrets over 𝔽₂. - We present a general rate-amplification technique for HSS that improves the download rate at the cost of requiring more shares. As a corollary, we get high-rate variants of computationally secure HSS schemes and efficient private information retrieval protocols from the literature. - We show that, in some cases, one can beat the best download rate of linear HSS by allowing nonlinear output reconstruction and 2^{-Ω(𝓁)} error probability.
Cite as

Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, and Mary Wootters. On the Download Rate of Homomorphic Secret Sharing. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 71:1-71:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fosli_et_al:LIPIcs.ITCS.2022.71,
  author =	{Fosli, Ingerid and Ishai, Yuval and Kolobov, Victor I. and Wootters, Mary},
  title =	{{On the Download Rate of Homomorphic Secret Sharing}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{71:1--71:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.71},
  URN =		{urn:nbn:de:0030-drops-156675},
  doi =		{10.4230/LIPIcs.ITCS.2022.71},
  annote =	{Keywords: Information-theoretic cryptography, homomorphic secret sharing, private information retrieval, secure multiparty computation, regenerating codes}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.117
Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data

Authors: Noah Shutty and Mary Wootters

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We study the problem of efficiently computing on encoded data. More specifically, we study the question of low-bandwidth computation of functions F:F^k → F of some data 𝐱 ∈ F^k, given access to an encoding 𝐜 ∈ Fⁿ of 𝐱 under an error correcting code. In our model - relevant in distributed storage, distributed computation and secret sharing - each symbol of 𝐜 is held by a different party, and we aim to minimize the total amount of information downloaded from each party in order to compute F(𝐱). Special cases of this problem have arisen in several domains, and we believe that it is fruitful to study this problem in generality. Our main result is a low-bandwidth scheme to compute linear functions for Reed-Solomon codes, even in the presence of erasures. More precisely, let ε > 0 and let 𝒞: F^k → Fⁿ be a full-length Reed-Solomon code of rate 1 - ε over a field F with constant characteristic. For any γ ∈ [0, ε), our scheme can compute any linear function F(𝐱) given access to any (1 - γ)-fraction of the symbols of 𝒞(𝐱), with download bandwidth O(n/(ε - γ)) bits. In contrast, the naive scheme that involves reconstructing the data 𝐱 and then computing F(𝐱) uses Θ(n log n) bits. Our scheme has applications in distributed storage, coded computation, and homomorphic secret sharing.
Cite as

Noah Shutty and Mary Wootters. Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{shutty_et_al:LIPIcs.ITCS.2022.117,
  author =	{Shutty, Noah and Wootters, Mary},
  title =	{{Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{117:1--117:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.117},
  URN =		{urn:nbn:de:0030-drops-157130},
  doi =		{10.4230/LIPIcs.ITCS.2022.117},
  annote =	{Keywords: Reed-Solomon Codes, Regenerating Codes, Coded Computation}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021
LIPIcs, Volume 207, APPROX/RANDOM 2021, Complete Volume

Authors: Mary Wootters and Laura Sanità

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
LIPIcs, Volume 207, APPROX/RANDOM 2021, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 1-1240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{wootters_et_al:LIPIcs.APPROX/RANDOM.2021,
  title =	{{LIPIcs, Volume 207, APPROX/RANDOM 2021, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{1--1240},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021},
  URN =		{urn:nbn:de:0030-drops-146929},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021},
  annote =	{Keywords: LIPIcs, Volume 207, APPROX/RANDOM 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mary Wootters and Laura Sanità

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{wootters_et_al:LIPIcs.APPROX/RANDOM.2021.0,
  author =	{Wootters, Mary and Sanit\`{a}, Laura},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{0:i--0:x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.0},
  URN =		{urn:nbn:de:0030-drops-146933},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.5
Sharp Threshold Rates for Random Codes

Authors: Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Suppose that 𝒫 is a property that may be satisfied by a random code C ⊂ Σⁿ. For example, for some p ∈ (0,1), 𝒫 might be the property that there exist three elements of C that lie in some Hamming ball of radius pn. We say that R^* is the threshold rate for 𝒫 if a random code of rate R^* + ε is very likely to satisfy 𝒫, while a random code of rate R^* - ε is very unlikely to satisfy 𝒫. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably "symmetric." For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property 𝒫 above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
Cite as

Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Sharp Threshold Rates for Random Codes. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.5,
  author =	{Guruswami, Venkatesan and Mosheiff, Jonathan and Resch, Nicolas and Silas, Shashwat and Wootters, Mary},
  title =	{{Sharp Threshold Rates for Random Codes}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.5},
  URN =		{urn:nbn:de:0030-drops-135446},
  doi =		{10.4230/LIPIcs.ITCS.2021.5},
  annote =	{Keywords: Coding theory, Random codes, Sharp thresholds}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2020.3
List-Decodability of Structured Ensembles of Codes (Invited Talk)

Authors: Mary Wootters

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
What combinatorial properties are satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball? What about any cube? In this talk, I will discuss the answer to these questions, along with a more general characterization of the properties that are likely to be satisfied by a random subspace. The motivation for this characterization comes from error correcting codes. I will discuss how to use this characterization to make progress on the questions of list-decoding and list-recovery for random linear codes, and also to establish the list-decodability of random Low Density Parity-Check (LDPC) codes. This talk is based on the works [Mosheiff et al., 2019] and [Guruswami et al., 2020], which are joint works with Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas.
Cite as

Mary Wootters. List-Decodability of Structured Ensembles of Codes (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 3:1-3:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wootters:LIPIcs.MFCS.2020.3,
  author =	{Wootters, Mary},
  title =	{{List-Decodability of Structured Ensembles of Codes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{3:1--3:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.3},
  URN =		{urn:nbn:de:0030-drops-126742},
  doi =		{10.4230/LIPIcs.MFCS.2020.3},
  annote =	{Keywords: Error Correcting Codes, List-Decoding}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.9
Bounds for List-Decoding and List-Recovery of Random Linear Codes

Authors: Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
A family of error-correcting codes is list-decodable from error fraction p if, for every code in the family, the number of codewords in any Hamming ball of fractional radius p is less than some integer L that is independent of the code length. It is said to be list-recoverable for input list size 𝓁 if for every sufficiently large subset of codewords (of size L or more), there is a coordinate where the codewords take more than 𝓁 values. The parameter L is said to be the "list size" in either case. The capacity, i.e., the largest possible rate for these notions as the list size L → ∞, is known to be 1-h_q(p) for list-decoding, and 1-log_q 𝓁 for list-recovery, where q is the alphabet size of the code family. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below q is the alphabet size, and ε > 0 is the gap to capacity). - A random linear code of rate 1 - log_q(𝓁) - ε requires list size L ≥ 𝓁^{Ω(1/ε)} for list-recovery from input list size 𝓁. This is surprisingly in contrast to completely random codes, where L = O(𝓁/ε) suffices w.h.p. - A random linear code of rate 1 - h_q(p) - ε requires list size L ≥ ⌊ {h_q(p)/ε+0.99}⌋ for list-decoding from error fraction p, when ε is sufficiently small. - A random binary linear code of rate 1 - h₂(p) - ε is list-decodable from average error fraction p with list size with L ≤ ⌊ {h₂(p)/ε}⌋ + 2. (The average error version measures the average Hamming distance of the codewords from the center of the Hamming ball, instead of the maximum distance as in list-decoding.) The second and third results together precisely pin down the list sizes for binary random linear codes for both list-decoding and average-radius list-decoding to three possible values. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset - or some symbol-wise permutation of it - lies in a random linear code with high probability. This uses a recent characterization of (Mosheiff, Resch, Ron-Zewi, Silas, Wootters, 2019) of configurations of codewords that are contained in random linear codes. Our upper bound follows from a refinement of the techniques of (Guruswami, Håstad, Sudan, Zuckerman, 2002) and strengthens a previous result of (Li, Wootters, 2018), which applied to list-decoding rather than average-radius list-decoding.
Cite as

Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for List-Decoding and List-Recovery of Random Linear Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2020.9,
  author =	{Guruswami, Venkatesan and Li, Ray and Mosheiff, Jonathan and Resch, Nicolas and Silas, Shashwat and Wootters, Mary},
  title =	{{Bounds for List-Decoding and List-Recovery of Random Linear Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.9},
  URN =		{urn:nbn:de:0030-drops-126126},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.9},
  annote =	{Keywords: list-decoding, list-recovery, random linear codes, coding theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.58
Sparse Recovery for Orthogonal Polynomial Transforms

Authors: Anna Gilbert, Albert Gu, Christopher Ré, Atri Rudra, and Mary Wootters

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper we consider the following sparse recovery problem. We have query access to a vector 𝐱 ∈ ℝ^N such that x̂ = 𝐅 𝐱 is k-sparse (or nearly k-sparse) for some orthogonal transform 𝐅. The goal is to output an approximation (in an 𝓁₂ sense) to x̂ in sublinear time. This problem has been well-studied in the special case that 𝐅 is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time O(k ⋅ polylog N). However, for transforms 𝐅 other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublinear-time algorithms - running in time poly(k log(N)) - for solving the sparse recovery problem for orthogonal transforms 𝐅 that arise from orthogonal polynomials. More precisely, our algorithm works for any 𝐅 that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the k-sparse sparse recovery problem to the 1-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials. Frequently, sparse FFT algorithms are described as implementing such a reduction; however, the technical details of such works are quite specific to the Fourier transform and moreover the actual implementations of these algorithms do not use the 1-sparse algorithm as a black box. In this work we give a reduction that works for a broad class of orthogonal polynomial families, and which uses any 1-sparse recovery algorithm as a black box.
Cite as

Anna Gilbert, Albert Gu, Christopher Ré, Atri Rudra, and Mary Wootters. Sparse Recovery for Orthogonal Polynomial Transforms. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gilbert_et_al:LIPIcs.ICALP.2020.58,
  author =	{Gilbert, Anna and Gu, Albert and R\'{e}, Christopher and Rudra, Atri and Wootters, Mary},
  title =	{{Sparse Recovery for Orthogonal Polynomial Transforms}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.58},
  URN =		{urn:nbn:de:0030-drops-124653},
  doi =		{10.4230/LIPIcs.ICALP.2020.58},
  annote =	{Keywords: Orthogonal polynomials, Jacobi polynomials, sublinear algorithms, sparse recovery}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.38
Lifted Multiplicity Codes and the Disjoint Repair Group Property

Authors: Ray Li and Mary Wootters

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we call lifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the t-disjoint-repair-group property than previously known constructions. More precisely, we show that, for t <=sqrt{N}, lifted multiplicity codes with length N and redundancy O(t^{0.585} sqrt{N}) have the property that any symbol of a codeword can be reconstructed in t different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant t < sqrt{N}. We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest.
Cite as

Ray Li and Mary Wootters. Lifted Multiplicity Codes and the Disjoint Repair Group Property. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2019.38,
  author =	{Li, Ray and Wootters, Mary},
  title =	{{Lifted Multiplicity Codes and the Disjoint Repair Group Property}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.38},
  URN =		{urn:nbn:de:0030-drops-112539},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.38},
  annote =	{Keywords: Lifted codes, Multiplicity codes, Disjoint repair group property, PIR code, Coding theory}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.46
Unconstraining Graph-Constrained Group Testing

Authors: Bruce Spang and Mary Wootters

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
In network tomography, one goal is to identify a small set of failed links in a network using as little information as possible. One way of setting up this problem is called graph-constrained group testing. Graph-constrained group testing is a variant of the classical combinatorial group testing problem, where the tests that one is allowed are additionally constrained by a graph. In this case, the graph is given by the underlying network topology. The main contribution of this work is to show that for most graphs, the constraints imposed by the graph are no constraint at all. That is, the number of tests required to identify the failed links in graph-constrained group testing is near-optimal even for the corresponding group testing problem with no graph constraints. Our approach is based on a simple randomized construction of tests. To analyze our construction, we prove new results about the size of giant components in randomly sparsified graphs. Finally, we provide empirical results which suggest that our connected-subgraph tests perform better not just in theory but also in practice, and in particular perform better on a real-world network topology.
Cite as

Bruce Spang and Mary Wootters. Unconstraining Graph-Constrained Group Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{spang_et_al:LIPIcs.APPROX-RANDOM.2019.46,
  author =	{Spang, Bruce and Wootters, Mary},
  title =	{{Unconstraining Graph-Constrained Group Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.46},
  URN =		{urn:nbn:de:0030-drops-112615},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.46},
  annote =	{Keywords: Group testing, network tomography, random graphs}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.50
Improved List-Decodability of Random Linear Binary Codes

Authors: Ray Li and Mary Wootters

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate 1 - H(p) - epsilon is (p,O(1/epsilon))-list-decodable with high probability. In this work, we show that such codes are (p, H(p)/epsilon + 2)-list-decodable with high probability, for any p in (0, 1/2) and epsilon > 0. In addition to improving the constant in known list-size bounds, our argument - which is quite simple - works simultaneously for all values of p, while previous works obtaining L = O(1/epsilon) patched together different arguments to cover different parameter regimes. Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear binary codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain a tight lower bound of 1/epsilon on the list size of uniformly random binary codes; this implies that random linear binary codes are in fact more list-decodable than uniformly random binary codes, in the sense that the list sizes are strictly smaller. To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear binary codes and (b) to prove a similar result for random linear rank-metric codes.
Cite as

Ray Li and Mary Wootters. Improved List-Decodability of Random Linear Binary Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2018.50,
  author =	{Li, Ray and Wootters, Mary},
  title =	{{Improved List-Decodability of Random Linear Binary Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.50},
  URN =		{urn:nbn:de:0030-drops-94547},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.50},
  annote =	{Keywords: List-decoding, Random linear codes, Rank-metric codes}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.43
Locality via Partially Lifted Codes

Authors: S. Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
In error-correcting codes, locality refers to several different ways of quantifying how easily a small amount of information can be recovered from encoded data. In this work, we study a notion of locality called the s-Disjoint-Repair-Group Property (s-DRGP). This notion can interpolate between two very different settings in coding theory: that of Locally Correctable Codes (LCCs) when s is large - a very strong guarantee - and Locally Recoverable Codes (LRCs) when s is small - a relatively weaker guarantee. This motivates the study of the s-DRGP for intermediate s, which is the focus of our paper. We construct codes in this parameter regime which have a higher rate than previously known codes. Our construction is based on a novel variant of the lifted codes of Guo, Kopparty and Sudan. Beyond the results on the s-DRGP, we hope that our construction is of independent interest, and will find uses elsewhere.
Cite as

S. Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters. Locality via Partially Lifted Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{frankfischer_et_al:LIPIcs.APPROX-RANDOM.2017.43,
  author =	{Frank-Fischer, S. Luna and Guruswami, Venkatesan and Wootters, Mary},
  title =	{{Locality via Partially Lifted Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.43},
  URN =		{urn:nbn:de:0030-drops-75922},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.43},
  annote =	{Keywords: Error correcting codes, locality, lifted codes}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact